package org.hot100_1;

public class leetcode83 {
//    public int maxProduct(int[] nums) {
//
//        int n = nums.length;
//        if (n==0){
//            return 0;
//        }
//        //dpMax[i]表示以num[i]结尾的子数组的乘积最大值
//        int [] dpMax =new int[n];
//        //dpMin[i]表示以num[i]结尾的子数组的乘积最小值，dpMin是为dpMax更新的
//        int [] dpMin =new int[n];
//        dpMax[0]=nums[0];
//        dpMin[0]=nums[0];
//
//        int max =nums[0];
//        for (int i = 1; i <n; i++) {
//            //dpMax的取值情况分为三种，取下面三种的最大值
//            //1、num[i]之前的乘积为负数，num[i]>0。那么dpMax=num[i]
//            //2、num[i]之前的乘积为正数，num[i]>0。那么dpMax=num[i]*dpMax[i-1]
//            //3、num[i]之前的乘积为负数，num[i]<0。那么dpMax=num[i]*dpMin[i-1]
//            dpMax[i]=Math.max(dpMin[i-1]*nums[i],Math.max(dpMax[i-1]*nums[i],nums[i]));
//
//            dpMin[i]=Math.min(dpMin[i-1]*nums[i],Math.min(dpMax[i-1]*nums[i],nums[i]));
//
//            max=Math.max(max,dpMax[i]);
//        }
//
//        return max;
//    }

    public int maxProduct(int[] nums) {
        int n = nums.length;
        //max取 nums[0]而不取Integer的最大值是因为当nums中只有一个的值，会导致遗漏
        int max = nums[0];
        int [] dpMax = new int[n];
        int [] dpMin = new int[n];
        dpMax[0]=nums[0];
        dpMin[0]=nums[0];
        for (int i = 1; i < n; i++) {
            dpMax[i]=Math.max(nums[i]*dpMax[i-1],Math.max(nums[i]*dpMin[i-1],nums[i]));
            dpMin[i]=Math.min(nums[i]*dpMax[i-1],Math.min(nums[i]*dpMin[i-1],nums[i]));
            max=Math.max(max,dpMax[i]);
        }

        return max;
    }
}
